package com.explorati.LeetCode014.longestCommonPrefix;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 18:01 2020/9/20 0020
 * @ Description ：
 */
public class Solution {
    /**
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 如果不存在公共前缀，返回空字符串 ""。
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        /**
         * 1. 加入传来的是空字符串，直接返回""
         * 2. 从第一个字符串入手，依次向后找最大公共前缀
         */
        if(strs.length == 0) {
            return "";
        }

        String res = strs[0];

        for(int i = 1; i < strs.length; i++) {
            String str = strs[i];
            for(int j = 0; j < str.length() && j < res.length();) {
                if(str.charAt(j) == res.charAt(j)) {
                    j ++;
                } else {
                    res = res.substring(0, j);
                    break;
                }
            }
            //如果此时res为空，直接返回
            if(res.length() == 0) {
                return "";
            }
            //如果res的长度大于此时遍历的str的长度，说明str中的字符完全满足res的字符，两者取交集应该为小的一方，即str
            if(res.length() > str.length()) {
                res = str;
            }
        }
        return res;
    }
}
